/**
 * Created by zhang_j on 2020/7/7
 */
public class 路径总和 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);
        System.out.println(hasPathSum(root, 22));

        TreeNode node1 = new TreeNode(1);
        node1.left = new TreeNode(2);
        System.out.println(hasPathSum(node1, 1));

        TreeNode node2 = new TreeNode(-2);
        node2.left = new TreeNode(-3);
        System.out.println(hasPathSum(node2, -5));
    }

    public static boolean hasPathSum(TreeNode root, int sum) {
        return isMatch(root, 0, sum);
    }

    private static boolean isMatch(TreeNode root, int count, int sum){
        if(root == null){
            return false;
        }
        count += root.val;
        if(root.left == null && root.right == null){
            return count == sum;
        }else{
            return isMatch(root.left, count, sum) | isMatch(root.right, count, sum);
        }
    }
}
